/*
 * @Author: 缄默
 * @Date: 2022-03-09 19:14:17
 * @LastEditors: 缄默
 * @LastEditTime: 2022-03-09 20:00:17
 */

//数组中的最长连续序列

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int longestConsecutive(vector<int>& arr);

int main() {
    vector<int> arr({100, 4, 200, 1, 3, 2});
    cout << longestConsecutive(arr) << endl;
    return 0;
}


int longestConsecutive(vector<int>& arr) {
    map<int, int> hashMap;
    int max = 0;
    for (auto num : arr) {
        //判断hashmap是否存在num 存在跳过不存在进行处理
        if (hashMap.count(num) == 0) {
            hashMap[num] = 1;
            //加入hashmap 判断下边是否有与其相连的
            if (hashMap.count(num - 1) == 1 ) {
                hashMap[num] += hashMap[num - 1];
                hashMap[num - hashMap[num - 1]] = hashMap[num];
            }
            //加入hashmap 判断上边是否有与其相连的
            if (hashMap.count(num + 1) == 1) {
                hashMap[num] += hashMap[num + 1];
                hashMap[num + hashMap[num + 1]] = hashMap[num];
                
                //是否存在上下均相连 若都是还需在修改下边相连的
                if (hashMap.count(num - 1) == 1 ) {
                    hashMap[num - hashMap[num - 1]] = hashMap[num];
                }
            }
            //整个过程只考虑边界与当前最大返回值
            max = max < hashMap[num] ? hashMap[num] : max;
        }
    }
    return max;
}